#include <stdio.h>
#include <limits.h>

#define SIZE 6

// 计算最短路径
void dijkstra(int graph[SIZE][SIZE], int source)
{
    int dist[SIZE];          // 存储从源节点到各节点的最短距离
    int visited[SIZE] = {0}; // 标记节点是否已被访问

    // 初始化距离数组
    for (int i = 0; i < SIZE; i++)
    {
        dist[i] = INT_MAX;
    }

    dist[source] = 0; // 源节点到自身的距离为0

    // 寻找最短路径
    for (int count = 0; count < SIZE - 1; count++)
    {
        int minDist = INT_MAX;
        int minIndex;

        // 选择当前未访问节点中距离最小的节点
        for (int v = 0; v < SIZE; v++)
        {
            if (visited[v] == 0 && dist[v] <= minDist)
            {
                minDist = dist[v];
                minIndex = v;
            }
        }

        // 标记该节点为已访问
        visited[minIndex] = 1;

        // 更新其他节点的最短距离
        for (int v = 0; v < SIZE; v++)
        {
            if (!visited[v] && graph[minIndex][v] && dist[minIndex] != INT_MAX && dist[minIndex] + graph[minIndex][v] < dist[v])
            {
                dist[v] = dist[minIndex] + graph[minIndex][v];
            }
        }
    }

    // 打印最短距离
    // printf("节点\t最短距离\n");
    printf("node\tshort\n");
    for (int i = 0; i < SIZE; i++)
    {
        printf("%d\t%d\n", i, dist[i]);
    }
}

void danceParty(int m, int n) {
    if (m == 0 || n == 0) {
        return;
    }

    int boyCount = m;
    int girlCount = n;

    printf("舞伴配对开始！\n");

    while (boyCount > 0 && girlCount > 0) {
        printf("男生 %d 和女生 %d 配对跳舞\n", m - boyCount + 1, n - girlCount + 1);
        boyCount--;
        girlCount--;

        // 模拟下一曲开始，判断是否还有剩余的男生和女生
        if (boyCount == 0 || girlCount == 0) {
            break;
        }

        // 输出未配对成功的男生和女生
        printf("等待下一曲的男生：");
        for (int i = m - boyCount + 1; i <= m; i++) {
            printf("%d ", i);
        }
        printf("\n");

        printf("等待下一曲的女生：");
        for (int i = n - girlCount + 1; i <= n; i++) {
            printf("%d ", i);
        }
        printf("\n");
    }

    printf("舞伴配对结束！\n");
}


int main()
{
   //  要求在某个节点上建一个健身房，使所有节点到健身房的路程最小；约定相邻节点间的距离为1；
    // 使用邻接矩阵来表示图，因为相邻节点间的距离是1，所以矩阵中的1表示两个节点之间有边相连，0表示没有。source变量表示健身房所在的节点，默认为2。
    int graph[SIZE][SIZE] = {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0},
        {1, 0, 0, 1, 1, 0},
        {0, 1, 1, 0, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {0, 0, 0, 1, 1, 0}
        };

    int source = 2; // 健身房所在的节点

    dijkstra(graph, source);


    int m = 5; // 男生人数
    int n = 3; // 女生人数

    danceParty(m, n);

    return 0;
}
